package com.c2b.algorithm.leetcode.base.sliding_window;

import java.util.Arrays;

/**
 * <a href="https://leetcode.cn/problems/minimum-window-substring/description/">字符串的排列(Permutation in String)</a>
 * <p>给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。</p>
 * <p>换句话说，s1 的排列之一是 s2 的 子串 。</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：s1 = "ab" s2 = "eidbaooo"
 *      输出：true
 *      解释：s2 包含 s1 的排列之一 ("ba").
 *
 * 示例 2：
 *      输入：s1= "ab" s2 = "eidboaoo"
 *      输出：false
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 *     <ul>
 *         <li>1 <= s1.length, s2.length <= 10^4</li>
 *         <li>s1 和 s2 仅包含小写字母</li>
 *     </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/10/25 18:11
 */
public class LC0567PermutationInString_M {
    static class Solution {
        public boolean checkInclusion(String s1, String s2) {
            // s1 是较短的字符，s2 是较长的字符
            int s1Len = s1.length();
            int s2Len = s2.length();
            if (s1Len > s2Len) {
                return false;
            }
            // 在字符串s2中维护一个长度为 s1Len的窗口。并统计窗口各个字符的频次
            int[] s1CntArr = new int[26];
            int[] s2CntArr = new int[26];
            for (int i = 0; i < s1Len; i++) {
                s1CntArr[s1.charAt(i) - 'a']++;
                s2CntArr[s2.charAt(i) - 'a']++;
            }
            // 如果窗口内字符出现的频次 和 s1窗口内字符出现的频次一样。返回 true
            if (Arrays.equals(s1CntArr, s2CntArr)) {
                return true;
            }
            for (int i = s1Len; i < s2Len; i++) {
                // s2 每次移除窗口中的第一个元素。并将当前元素添加到窗口中
                s2CntArr[s2.charAt(i - s1Len) - 'a']--;
                s2CntArr[s2.charAt(i) - 'a']++;
                if (Arrays.equals(s1CntArr, s2CntArr)) {
                    return true;
                }
            }
            return false;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.checkInclusion("ab", "eidbaooo"));
        System.out.println(solution.checkInclusion("ab", "eidboaoo"));
    }
}
